package chapter21;

/**
 * 用于不相交的数据结构-链表
 * <p>
 * rank秩,根据秩进行路径压缩的合并
 */
public class Link {

    public static void markSet(Node x) {
        x.p = x;
        x.rank = 0;
    }

    /**
     * 联合两个节点的root节点
     */
    public static void union(Node x, Node y) {
        link(findSet(x), findSet(y));
    }

    /**
     * 按秩rank合并.大的rank做父节点,rank相等要自增
     */
    private static void link(Node x, Node y) {
        if (x.rank > y.rank) {
            y.p = x;
        } else {
            x.p = y;
            if (x.rank == y.rank) {
                y.rank++;
            }
        }
    }

    /**
     * 找到x的root节点
     */
    public static Node findSet(Node x) {
        if (x != x.p) {
            x.p = findSet(x.p);
        }
        return x.p;
    }

    public static class Node {
        public Node p;
        public int rank;
        public String key;

        public Node(String key) {
            this.key = key;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "p=" + (this.key.equals(p.key) ? null : p) +
                    ", rank=" + rank +
                    ", key='" + key + '\'' +
                    '}';
        }
    }

}
